package _linklist

/**
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
 * https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html
 *
 * 19. 删除链表的倒数第 N 个结点
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 */
class leetcode_19 {
    class ListNode(var `val`: Int) {
        var next: ListNode? = null
    }

    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        /**
        1   2   3       4(x)   5    NULL
        dummy/slow / fast ->
        dummy ->                    slow                fast

        while - 先让fast 快走N+1步
        结束条件：count 0，slow为空

        while - 同时走fast 和 slow，直到 fast 为 空
        结束条件：fast 为空
         */

        // S - N
        // T - 1
        val dummy: ListNode = ListNode(-1)
        dummy.next = head

        var slow: ListNode? = dummy
        var fast: ListNode? = dummy
        var count: Int = n + 1
        while (count > 0 && fast != null) {
            fast = fast?.next
            count--
        }

        while (fast != null) {
            fast = fast?.next
            slow = slow?.next
        }

        slow?.next = slow?.next?.next
        return dummy.next
    }
}